/*******************************************
 * Copyright 2007 Aphrodite Framework for javaME .
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the GNU Public License v2.0
 * which accompanies this distribution, and is available at
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * Email : owner@aphroditeme.dev.java.net
 * Contributors:
 *     Kent Elton - initial API and implementation
 *******************************************/

package com.aphrodite.util;

/**
 * Routines for array manipulation, Sorting, Searching.
 * 
 * @author kentelt
 * 
 */
public final class ArrayUtil {
	private static int index;

	/**
	 * Add an object(<code>toAppend</code>) to a <code>src</code> array
	 * 
	 * @param src
	 * @param toAppend
	 * @return The appended array
	 */
	public static final Object[] append(Object[] src, Object[] toAppend) {
		Object[] dst = new Object[src.length + toAppend.length];
		System.arraycopy(src, 0, dst, 0, src.length);
		System.arraycopy(toAppend, 0, dst, dst.length - 1, toAppend.length);
		return dst;
	}

	public static final short[] append(short[] src, short[] toAppend) {
		short[] dst = new short[src.length + toAppend.length];
		System.arraycopy(src, 0, dst, 0, src.length);
		System.arraycopy(toAppend, 0, dst, dst.length - 1, toAppend.length);
		return dst;
	}

	private static int bSearch0(char ac[], int start, int length, char c) {
		int k = start;
		for (int l = length - 1; k <= l;) {
			int i1 = k + l >>> 1;
			char c1 = ac[i1];
			if (c1 < c)
				k = i1 + 1;
			else if (c1 > c)
				l = i1 - 1;
			else
				return i1;
		}
		return -(k + 1);
	}

	private static int bSearch0(String aobj[], int i, int j, String obj) {
		int k = i;
		for (int l = j - 1; k <= l;) {
			int i1 = k + l >>> 1;
			int j1 = aobj[i1].compareTo(obj);
			if (j1 < 0)
				k = i1 + 1;
			else if (j1 > 0)
				l = i1 - 1;
			else
				return i1;
		}
		return -(k + 1);
	}

	/**
	 * Casts the given input array into the output array
	 * 
	 * @param input
	 *            the input array
	 * @param output
	 *            the output array
	 * @return Output array
	 */
	public static Object[] cast(Object[] input, Object[] output) {
		if (input == null) {
			return null;
		}
		System.arraycopy(input, 0, output, 0, Math.min(input.length, output.length));
		return output;
	}

	public static boolean equals(int[] array1, int[] arrary2) {
		if (array1 == arrary2)
			return true;
		else if (array1.length != arrary2.length) {
			return false;
		} else {
			for (int i = 0; i < array1.length; i++) {
				if (array1[i] != arrary2[i])
					return false;
			}
			return true;
		}
	}

	// private static int binarySearch0(byte abyte0[], int start, int length,
	// byte byte0) {
	// int k = start;
	// for (int l = length - 1; k <= l;) {
	// int i1 = k + l >>> 1;
	// byte byte1 = abyte0[i1];
	// if (byte1 < byte0)
	// k = i1 + 1;
	// else if (byte1 > byte0)
	// l = i1 - 1;
	// else
	// return i1;
	// }
	//
	// return -(k + 1);
	// }

	/**
	 * 
	 * @param obj1
	 *            first array of objects
	 * @param obj2
	 *            second array of objects
	 * @return <code>True</code> if the two arrays are equal
	 */
	public static boolean equals(Object[] obj1, Object[] obj2) {
		if (obj1 == obj2)
			return true;
		else if (obj1.length != obj2.length) {
			return false;
		} else {
			for (int i = 0; i < obj1.length; i++) {
				Object obj = obj1[i];
				Object obj3 = obj2[i];
				if (obj != null ? !obj.equals(obj3) : obj3 != null)
					return false;

			}
			return true;
		}
	}

	/**
	 * Find the largest value in an array of primitives.
	 * 
	 * @param array
	 * @param startIndex
	 *            0 based index
	 * @param endIndex
	 *            1 based index
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code> startIndex</code> or <code>endIndex</code> is
	 *             invalid.
	 * @throws NullPointerException
	 *             if <code>array</code> is null
	 * @return Biggest value in <code>array</code>
	 */
	public static synchronized final int getBiggestValue(Object array, int startIndex, int endIndex) {
		int biggest = 0;
		if (array instanceof byte[]) {
			byte[] tmp = (byte[]) array;
			biggest = tmp[0];
			for (int i = startIndex; i < endIndex; i++) {
				if (tmp[i] > biggest) {
					biggest = tmp[i];
					index = i;
				}
			}
		} else if (array instanceof short[]) {
			short[] tmp = (short[]) array;
			biggest = tmp[0];
			for (int i = startIndex; i < endIndex; i++) {
				if (tmp[i] > biggest) {
					biggest = tmp[i];
					index = i;
				}
			}
		} else if (array instanceof int[]) {
			int[] tmp = (int[]) array;
			biggest = tmp[0];
			for (int i = startIndex; i < endIndex; i++) {
				if (tmp[i] > biggest) {
					biggest = tmp[i];
					index = i;
				}
			}
		} else {
			index = -1;
		}
		return biggest;
	}

	/**
	 * Returns the index of the biggest value in a primitive array
	 * 
	 * @param array
	 * @param startIndex
	 *            0 based index
	 * @param endIndex
	 *            1 based index * @throws NullPointerException if
	 *            <code>array</code> is <code>null</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code> startIndex</code> or <code>endIndex</code> is
	 *             invalid.
	 * @return Index of the biggest value. -1 if < code>array</code> is not a
	 *         supported type
	 */
	public static final int getBiggestValueIndex(Object array, int startIndex, int endIndex) {
		getBiggestValue(array, startIndex, endIndex);
		return index;
	}

	/**
	 * Returns the sum of a long array
	 * 
	 * @param array
	 *            To sum up
	 * @throws NullPointerException
	 *             if <code>array</code> is <code>null</code>
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code> startIndex</code> or <code>endIndex</code> is
	 *             invalid.
	 * @return Sum of all the elements in <code>array</code>
	 */
	public static long getSum(long[] array, int startIndex, int endIndex) {
		long temp = 0;
		for (int i = 0; i < array.length; i++) {
			temp += array[i];
		}
		return temp;
	}

	/**
	 * Get the sum of the contents of a primitive array.
	 * 
	 * @param array
	 *            An array of primitives. Except array of <code>long</code>
	 *            {@link ArrayUtil#getSum(long[])}
	 * @throws NullPointerException
	 *             if <code>array</code> is null
	 * @throws ArrayIndexOutOfBoundsException
	 *             if <code> startIndex</code> or <code>endIndex</code> is
	 *             invalid
	 * @return Sum of the elements in the array. 0 if its an unsupported array
	 */
	public static int getSum(Object array, int startIndex, int endIndex) {
		int temp = 0;
		if (array instanceof byte[]) {
			final byte[] tmp = (byte[]) array;
			for (int i = startIndex; i < endIndex; i++) {
				temp += tmp[i];
			}
		} else if (array instanceof short[]) {
			final short[] tmp = (short[]) array;
			for (int i = startIndex; i < endIndex; i++) {
				temp += tmp[i];
			}
		} else if (array instanceof int[]) {
			final int[] tmp = (int[]) array;
			for (int i = startIndex; i < endIndex; i++) {
				temp += tmp[i];
			}
		}
		return temp;
	}

	/**
	 * Returns true if the array has repeated items
	 * <p>
	 * Null values are ignored
	 * </p>
	 * 
	 * @param array
	 * @return <code>true</code> if the <code>array</code> has duplicate
	 *         elements
	 */
	public static boolean hasDuplicateElements(Object[] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < i; j++) {
				Object o1 = array[i];
				Object o2 = array[j];
				if (o1 != null && o2 != null) {
					if (o1.equals(o2)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	private static int med3(char ac[], int i, int j, int k) {
		return ac[i] >= ac[j] ? ac[j] <= ac[k] ? ac[i] <= ac[k] ? i : k : j : ac[j] >= ac[k] ? ac[i] >= ac[k] ? i : k
				: j;
	}

	private static void mergeSort(String[] dest, String[] src, int offset, int length, int k) {
		int l = length - offset;
		if (l < 7) {
			for (int i1 = offset; i1 < length; i1++) {
				for (int k1 = i1; k1 > offset && (src[k1 - 1]).compareTo(src[k1]) > 0; k1--)
					swap(src, k1, k1 - 1);
			}

			return;
		}
		int j1 = offset;
		int l1 = length;
		offset += k;
		length += k;
		int i2 = offset + length >>> 1;
		mergeSort(src, dest, offset, i2, -k);
		mergeSort(src, dest, i2, length, -k);
		if ((dest[i2 - 1]).compareTo(dest[i2]) <= 0) {
			System.arraycopy(((dest)), offset, ((src)), j1, l);
			return;
		}
		int j2 = j1;
		int k2 = offset;
		int l2 = i2;
		for (; j2 < l1; j2++)
			if (l2 >= length || k2 < i2 && (dest[k2]).compareTo(dest[l2]) <= 0)
				src[j2] = dest[k2++];
			else
				src[j2] = dest[l2++];

	}

	/**
	 * Resize an array array (src values are maintained).
	 * 
	 * @param src
	 * @param newSize
	 * @return Array of int with the length of <code>newSize</code>
	 */
	public static final int[] resize(int[] src, int newSize) {
		int[] dst = new int[src.length + newSize];
		System.arraycopy(src, 0, dst, 0, src.length);
		return dst;
	}

	// ----------------DO NO DELETE THIS
	// private static void rangeCheck(int i, int j, int k) {
	// if (j > k)
	// throw new IllegalArgumentException((new
	// StringBuffer()).append("fromIndex(").append(j).append(
	// ") > toIndex(").append(k).append(")").toString());
	// if (j < 0)
	// throw new ArrayIndexOutOfBoundsException(j);
	// if (k > i)
	// throw new ArrayIndexOutOfBoundsException(k);
	// else
	// return;
	// }

	// public static int search(byte array[], byte byt) {
	// return binarySearch0(array, 0, array.length, byt);
	// }

	/**
	 * Resize an array array (src values are maintained).
	 * 
	 * @param src
	 * @param newSize
	 * @return
	 */
	public static final Object[] resize(Object[] src, int newSize) {
		Object[] dst = new Object[src.length + newSize];
		System.arraycopy(src, 0, dst, 0, src.length);
		return dst;
	}

	/**
	 * Performs a binary search of the <code>key</code> in the given character
	 * array
	 * 
	 * @param array
	 * @param key
	 * @return index of the search key in the array. -1 if not found
	 */
	public static int search(char array[], char key) {
		return bSearch0(array, 0, array.length, key);
	}

	/**
	 * Performs a binary search of the given <code>key> in the String array
	 * 
	 * @param array
	 * @param key
	 * @return index of the search
	 */
	public static int search(String[] array, String key) {
		return bSearch0(array, 0, array.length, key);
	}

	/**
	 * Sort the given array of characters
	 * 
	 * @param ac
	 */
	public static void sort(char[] ac) {
		sort1(ac, 0, ac.length);
	}

	// -----------------DO NO DELETE THIS
	// /**
	// *
	// * @param array
	// * @param fromIndex
	// * @param toIndex
	// * @throws IllegalArgumentException
	// * if (fromIndex > toIndex)
	// * @throws ArrayIndexOutOfBoundsException
	// * if (toIndex < 0)
	// * @throws ArrayIndexOutOfBoundsException
	// * if (toIndex > array.length)
	// *
	// */
	// private static void sort(char[] array, int fromIndex, int toIndex) {
	// // rangeCheck(array.length, fromIndex, toIndex);
	// sort1(array, fromIndex, toIndex - fromIndex);
	// }

	// ----------------------DO NO DELETE THIS
	// public int compareTo(String s1, String s2) {
	// int i = s1.length();
	// int j = s2.length();
	// int k = Math.min(i, j);
	// char ac[] = s1.toCharArray();
	// char ac1[] = s2.toCharArray();
	// int l = 0;// offset;
	// int i1 = 0;// s.offset;
	// if (l == i1) {
	// int j1 = l;
	// for (int k1 = k + l; j1 < k1; j1++) {
	// char c2 = ac[j1];
	// char c3 = ac1[j1];
	// if (c2 != c3)
	// return c2 - c3;
	// }
	//
	// } else {
	// while (k-- != 0) {
	// char c = ac[l++];
	// char c1 = ac1[i1++];
	// if (c != c1)
	// return c - c1;
	// }
	// }
	// return i - j;
	// }

	/**
	 * <p> Sorts the given array of string. </p> Sorting is performed with
	 * priortity to upper case characters.
	 * 
	 * @param array
	 * @throws NullPointerException
	 *             if the array is null
	 */
	public static void sort(String[] array) {
		if (array == null)
			throw new NullPointerException();
		String[] copy = new String[array.length];
		for (int i = 0; i < array.length; i++) {
			copy[i] = new String(array[i]);
		}
		mergeSort(copy, array, 0, array.length, 0);

	}

	private static void sort1(char ac[], int i, int j) {
		if (j < 7) {
			for (int k = i; k < j + i; k++) {
				for (int i1 = k; i1 > i && ac[i1 - 1] > ac[i1]; i1--)
					swap(ac, i1, i1 - 1);
			}
			return;
		}
		int l = i + (j >> 1);
		if (j > 7) {
			int j1 = i;
			int k1 = (i + j) - 1;
			if (j > 40) {
				int i2 = j / 8;
				j1 = med3(ac, j1, j1 + i2, j1 + 2 * i2);
				l = med3(ac, l - i2, l, l + i2);
				k1 = med3(ac, k1 - 2 * i2, k1 - i2, k1);
			}
			l = med3(ac, j1, l, k1);
		}
		char c = ac[l];
		int l1 = i;
		int j2 = l1;
		int k2 = (i + j) - 1;
		int l2 = k2;
		do {
			for (; j2 <= k2 && ac[j2] <= c; j2++)
				if (ac[j2] == c)
					swap(ac, l1++, j2);

			for (; k2 >= j2 && ac[k2] >= c; k2--)
				if (ac[k2] == c)
					swap(ac, k2, l2--);

			if (j2 > k2)
				break;
			swap(ac, j2++, k2--);
		} while (true);
		int j3 = i + j;
		int i3 = Math.min(l1 - i, j2 - l1);
		vecswap(ac, i, j2 - i3, i3);
		i3 = Math.min(l2 - k2, j3 - l2 - 1);
		vecswap(ac, j2, j3 - i3, i3);
		if ((i3 = j2 - l1) > 1)
			sort1(ac, i, i3);
		if ((i3 = l2 - k2) > 1)
			sort1(ac, j3 - i3, i3);
	}

	private static void swap(char ac[], int i, int j) {
		char c = ac[i];
		ac[i] = ac[j];
		ac[j] = c;
	}

	private static void swap(String[] aobj, int i, int j) {
		String obj = aobj[i];
		aobj[i] = aobj[j];
		aobj[j] = obj;
	}

	/*
	 * j2se adaptation
	 * 
	 * @param ac
	 * 
	 * @param i
	 * 
	 * @param j
	 * 
	 * @param k
	 */
	private static void vecswap(char ac[], int i, int j, int k) {
		for (int l = 0; l < k;) {
			swap(ac, i, j);
			l++;
			i++;
			j++;
		}
	}

	private ArrayUtil() {}
}
